package algorithm.node;//package org.example.algorithm.node;
//
/////**
//// * Your MyLinkedList object will be instantiated and called as such:
//// * MyLinkedList obj = new MyLinkedList();
//// * int param_1 = obj.get(index);
//// * obj.addAtHead(val);
//// * obj.addAtTail(val);
//// * obj.addAtIndex(index,val);
//// * obj.deleteAtIndex(index);
//// */
//
//class MyLinkedList {
//    // 实现单向链表，即每个节点仅存储本身的值和后继节点。
//    int size;  // 保存有效节点数。
//    ListNode dummyHead; //头节点（哨兵），便于处理。
//
//    public class ListNode{
//        int val;
//        ListNode next;
//        public ListNode(){}
//        public ListNode(int val){this.val = val; this.next = null;}
//    }
//
//    public MyLinkedList() {
//        //构造函数，对象初始化
//        this.dummyHead = new ListNode(-1);
//        this.size = 0;
//    }
//
//    public int get(int index) {
//        if( index < 0 || index >= size){
//            return -1;
//        }
//        ListNode cur = dummyHead;
//        for (int i = 0; i <= index; i++) {
//            cur = cur.next; // 遍历到 index的位置
//        }
//        return cur.val;
//    }
//
//    public void addAtHead(int val) {
//        addAtIndex(0,val);
//    }
//
//    public void addAtTail(int val) {
//        addAtIndex(size,val);
//    }
//
//    public void addAtIndex(int index, int val) {
//        if (index<0 || index > size){
//            return;
//        }
//        //因为有虚拟头结点，在头部和中间进行插入一样。尾部插入也可以是这两步不用再单独考虑
//        // 插入的话找前驱结点
//        ListNode newNode = new ListNode(val);
//        ListNode cur = dummyHead;
//        for (int i =0; i< index; i++){
//                cur = cur.next;// index的前一个位置
//        }
//
//        newNode.next = cur.next;
//        cur.next = newNode;
//
//        ++size;
//    }
//
//    public void deleteAtIndex(int index) {
//        if( index < 0 || index >= size){
//            return;
//        }
//        //删除节点，找前一个节点
//        ListNode cur = dummyHead;
//        for (int i = 0; i < index; i++) {
//            cur = cur.next;
//        }
//        cur.next = cur.next.next;
//        --size;
//    }
//}